package com.my.study.structures.tree;

/**
 * @author Carlos
 * @version 1.0
 * @Description 线索化二叉树
 *
 *
 *
 *
 * @date 2021/8/11 23:15
 **/
public class ThreadedBinaryTree {
    /** 根结点*/
    private HeroNode root;

    /** 为实现线索化，需要创建指向当前结点的前驱结点的指针*/
    private HeroNode preNode;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    /**
     * 线索化{@code HeroNode}node，
     *
     * @param node 需要线索化的结点
     */
    public void threadedNodes(HeroNode node) {
        if (node == null) {
            return;
        }
        // 1、线索化左子树
        threadedNodes(node.getLeft());
        // 2、线索化当前结点
        // 处理前驱结点
        if (node.getLeft() == null)  {
            // 左指针指向前驱结点
            node.setLeft(preNode);
            node.setLeftType(1);
        }

        // 处理后继结点
        if (preNode != null && node.getRight() == null) {
            preNode.setRight(node);
            preNode.setRightType(1);
        }
        // 每处理完一个结点，就让preNode指向node结点
        preNode = node;

        // 3、线索化右子树
        threadedNodes(node.getRight());
    }

}
